﻿#include <iostream>
#include <stdlib.h>
using namespace std;

int bs_unrecursive(int *a,int length, int key) {
	if (a == NULL)
		return -1;
	int low = 0;
	int high = length - 1;
	int mid = 0;
	while (low <= high)
	{
		mid = (low + high) / 2;
		if (a[mid] < key)
			low = mid + 1;
		else if (a[mid] > key)
			high = mid - 1;
		else
			return mid;
	}
	return -1;
}

int bs_recursive(int *a,int low,int high, int key) {
	if (a == NULL)
		return -1;
	if (low > high)
		return -1;
	int mid = (low + high) / 2;
	if (a[mid] == key)
		return mid;
	else if (a[mid] < key)
		return bs_recursive(a, mid + 1, high, key);
	else
		return bs_recursive(a, low, mid - 1, key);
}
int main()
{
	int array[10];
	for (int i = 0; i < 10; i++)
		array[i] = i;
	int length = sizeof(array) / sizeof(array[0]);
	cout << "No recursive:" << endl;
	cout << "position:" << bs_unrecursive(array,length, 6) << endl;
	cout << "recursive:" << endl;
	cout << "position:" << bs_recursive(array, 0, 9, 6) << endl;

	return 0;
}
